#ifndef __LIBHMAP_H
#define __LIBHMAP_H

#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 * C语言哈希表库（header-only）
 * 修复了hmap_remove中的内存释放问题，完善了键复制逻辑
 */

/**
 * @brief 哈希表节点结构
 */
typedef struct hmap_node_t {
    char *key;               /* 元素的键 */
    void *value;             /* 元素的值 */
    bool key_copied;         /* 标记键是否是通过strdup复制的 */
    struct hmap_node_t* next;/* 下一个节点 */
} hmap_node_t;

/**
 * @brief 哈希表结构
 */
typedef struct {
    hmap_node_t **arr;       /* 内部数组，存储链表头节点 */
    uint8_t cap;             /* 数组容量 */
    uint32_t size;           /* 元素数量 */
    float load_factor;       /* 负载因子 */
    void (*free_value)(void*);/* 自定义值释放函数 */
} hmap_t;

/**
 * @brief 哈希表迭代器
 */
typedef struct {
    hmap_t *map;             /* 所属哈希表 */
    uint8_t index;           /* 当前数组索引 */
    hmap_node_t* last;       /* 上一个访问的节点 */
} hmap_itr_t;

/* 哈希表操作函数声明 */
void hmap_new(hmap_t *hmap);
void hmap_new_cap(hmap_t *hmap, uint8_t cap);
void hmap_set_free_func(hmap_t *hmap, void (*free_func)(void*));
void* hmap_get(hmap_t *hmap, const char *key);
void hmap_put(hmap_t *hmap, const char *key, void *value, bool copy_key);
void hmap_remove(hmap_t *hmap, const char *key);
bool hmap_empty(hmap_t *hmap);
uint32_t hmap_size(hmap_t *hmap);

/* 迭代器函数声明 */
void hmap_itr_new(hmap_itr_t *itr, hmap_t *hmap);
hmap_node_t* hmap_itr_adv(hmap_itr_t *itr);

/* 其他函数声明 */
void hmap_free(hmap_t *hmap);
void hmap_print(hmap_t *hmap);

#endif // __LIBHMAP_H

#ifdef LIBHMAP_IMPLEMENTATION

#define __HMAP_DEFAULT_CAP 20
#define __HMAP_DEFAULT_LOAD_FACTOR 0.75f

/**
 * @brief 初始化指定容量的哈希表
 */
void hmap_new_cap(hmap_t *hmap, uint8_t cap)
{
    if (!hmap) return; // 空指针检查
    hmap->arr = calloc(cap, sizeof(hmap_node_t*));
    hmap->cap = cap;
    hmap->size = 0;
    hmap->load_factor = __HMAP_DEFAULT_LOAD_FACTOR;
    hmap->free_value = NULL;
}

/**
 * @brief 初始化默认容量的哈希表
 */
void hmap_new(hmap_t *hmap)
{
    if (!hmap) return; // 空指针检查
    hmap_new_cap(hmap, __HMAP_DEFAULT_CAP);
}

/**
 * @brief 设置自定义值释放函数
 */
void hmap_set_free_func(hmap_t *hmap, void (*free_func)(void*))
{
    if (hmap) {
        hmap->free_value = free_func;
    }
}

/**
 * @brief 获取哈希表元素数量
 */
uint32_t hmap_size(hmap_t *hmap)
{
    return hmap ? hmap->size : 0;
}

/**
 * @brief 哈希函数（djb2算法）
 */
static int hash_key(const char *key, uint8_t cap)
{
    if (!key || cap == 0) return 0; // 边界检查
    uint32_t hash = 5381;
    int c;
    while ((c = *key++)) {
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    }
    return hash % cap;
}

/**
 * @brief 在链表中查找节点
 */
static hmap_node_t* find_node(hmap_node_t* head, const char *key,
            bool need_prev, hmap_node_t** prev)
{
    if (!key) return NULL; // 空键检查
    hmap_node_t *temp = head;
    if (need_prev && prev) {
        *prev = NULL;
    }

    while (temp) {
        if (strcmp(key, temp->key) == 0) {
            return temp;
        }
        if (need_prev && prev) {
            *prev = temp;
        }
        temp = temp->next;
    }
    return NULL;
}

/**
 * @brief 哈希表扩容
 */
static void hmap_resize(hmap_t *hmap, uint8_t new_cap)
{
    if (!hmap || new_cap <= hmap->cap) return;

    hmap_node_t **new_arr = calloc(new_cap, sizeof(hmap_node_t*));
    if (!new_arr) return;

    // 重新哈希所有节点到新数组
    for (int i = 0; i < hmap->cap; i++) {
        hmap_node_t *current = hmap->arr[i];
        while (current) {
            hmap_node_t *next = current->next;
            int new_index = hash_key(current->key, new_cap);

            // 插入到新链表头部
            current->next = new_arr[new_index];
            new_arr[new_index] = current;

            current = next;
        }
    }

    free(hmap->arr);
    hmap->arr = new_arr;
    hmap->cap = new_cap;
}

/**
 * @brief 从哈希表获取元素
 */
void* hmap_get(hmap_t *hmap, const char *key)
{
    if (!hmap || !key) return NULL;

    int index = hash_key(key, hmap->cap);
    hmap_node_t *elem = find_node(hmap->arr[index], key, false, NULL);
    return (elem) ? elem->value : NULL;
}

/**
 * @brief 向哈希表插入元素
 */
void hmap_put(hmap_t *hmap, const char *key, void *value, bool copy_key)
{
    if (!hmap || !key) return;

    // 检查扩容
    if ((float)hmap->size / hmap->cap >= hmap->load_factor) {
        hmap_resize(hmap, hmap->cap * 2);
    }

    int index = hash_key(key, hmap->cap);
    hmap_node_t *elem = find_node(hmap->arr[index], key, false, NULL);

    if (elem) {
        // 键已存在，更新值
        if (hmap->free_value && elem->value) {
            hmap->free_value(elem->value);
        }
        elem->value = value;
    } else {
        // 新建节点
        hmap_node_t *new_node = malloc(sizeof(hmap_node_t));
        if (!new_node) return;

        // 处理键的复制
        if (copy_key) {
            new_node->key = strdup(key); // 复制键（需要手动释放）
            new_node->key_copied = true;
        } else {
            new_node->key = (char *)key; // 直接引用外部键
            new_node->key_copied = false;
        }

        new_node->value = value;
        new_node->next = hmap->arr[index]; // 插入到链表头部
        hmap->arr[index] = new_node;
        hmap->size++;
    }
}

/**
 * @brief 从哈希表移除元素（修复核心）
 */
void hmap_remove(hmap_t *hmap, const char *key)
{
    if (!hmap || !key || hmap_empty(hmap)) return;

    int index = hash_key(key, hmap->cap);
    hmap_node_t *prev = NULL;
    hmap_node_t *elem = find_node(hmap->arr[index], key, true, &prev);

    if (!elem) return; // 节点不存在

    // 从链表中移除节点
    if (hmap->arr[index] == elem) {
        // 移除头节点
        hmap->arr[index] = elem->next;
    } else {
        // 移除中间节点
        prev->next = elem->next;
    }

    // 释放资源（关键修复：只释放复制的键）
    if (elem->key_copied) {
        free(elem->key); // 仅当键是复制的才释放
    }
    // 释放值（如果有自定义释放函数）
    if (hmap->free_value && elem->value) {
        hmap->free_value(elem->value);
    }
    free(elem); // 释放节点本身

    hmap->size--;
}

/**
 * @brief 检查哈希表是否为空
 */
bool hmap_empty(hmap_t *hmap)
{
    return hmap ? (hmap->size == 0) : true;
}

/**
 * @brief 释放链表节点
 */
static void hmap_node_free(hmap_t *hmap, hmap_node_t* head)
{
    if (!hmap) return;

    hmap_node_t* temp;
    while (head) {
        temp = head;
        head = head->next;

        // 释放键（仅释放复制的）
        if (temp->key_copied) {
            free(temp->key);
        }
        // 释放值
        if (hmap->free_value && temp->value) {
            hmap->free_value(temp->value);
        }
        free(temp);
    }
}

/**
 * @brief 释放哈希表
 */
void hmap_free(hmap_t *hmap)
{
    if (!hmap) return;

    for (int i = 0; i < hmap->cap; i++) {
        hmap_node_free(hmap, hmap->arr[i]);
        hmap->arr[i] = NULL;
    }
    free(hmap->arr);
    hmap->arr = NULL;
    hmap->size = 0;
    hmap->cap = 0;
}

/**
 * @brief 迭代器前进
 */
hmap_node_t* hmap_itr_adv(hmap_itr_t *itr)
{
    if (!itr || !itr->map || hmap_empty(itr->map)) {
        return NULL;
    }

    // 未初始化迭代器：找第一个非空节点
    if (itr->index == itr->map->cap) {
        uint8_t i;
        for (i = 0; i < itr->map->cap && !itr->map->arr[i]; i++);
        if (i < itr->map->cap) {
            itr->last = itr->map->arr[i];
            itr->index = i;
            return itr->last;
        }
        return NULL;
    }

    // 遍历当前链表
    if (itr->last && itr->last->next) {
        itr->last = itr->last->next;
        return itr->last;
    }

    // 找下一个非空链表
    itr->index++;
    for (; itr->index < itr->map->cap && !itr->map->arr[itr->index]; itr->index++);
    if (itr->index < itr->map->cap) {
        itr->last = itr->map->arr[itr->index];
        return itr->last;
    }

    return NULL;
}

/**
 * @brief 初始化迭代器
 */
void hmap_itr_new(hmap_itr_t *itr, hmap_t *hmap)
{
    if (!itr || !hmap) return;
    itr->index = hmap->cap; // 标记未初始化
    itr->map = hmap;
    itr->last = NULL;
}

/**
 * @brief 打印链表节点
 */
static void hmap_print_node(hmap_node_t *head)
{
    hmap_node_t* temp = head;
    while (temp) {
        printf("(%s:%p)->", temp->key, temp->value);
        temp = temp->next;
    }
    printf("NULL\n");
}

/**
 * @brief 打印哈希表
 */
void hmap_print(hmap_t *hmap)
{
    if (!hmap) {
        printf("哈希表未初始化。\n");
        return;
    }

    printf("哈希表容量: %hhu, 元素数量: %u\n", hmap->cap, hmap->size);
    for (int i = 0; i < hmap->cap; i++) {
        printf("索引 %d: ", i);
        hmap_print_node(hmap->arr[i]);
    }
}

#endif // LIBHMAP_IMPLEMENTATION


/**
 * 主要修改点：

 将所有hmap_push调用改为hmap_put
 为hmap_put添加了第四个参数false（表示不复制键的内存）
 对头文件引用进行了标准化（假设头文件名为hmap.h）
 在迭代器测试中增加了空指针检查，使测试更健壮
 在itr_test中添加了hmap_free调用，避免内存泄漏

 功能扩展：
 新增hmap_put函数，支持键的内存复制（通过copy_key参数）
 添加了自动扩容功能，当负载因子达到阈值时自动扩容为原来的 2 倍
 增加了自定义值释放函数hmap_set_free_func，方便管理复杂类型的内存
 新增hmap_size函数，用于获取哈希表中的元素数量
 改进了哈希算法，使用更高效的 djb2 算法
 增强了迭代器功能，使其更健壮
 完善了内存管理，特别是键和值的释放逻辑

 Bug 修复：
 将u_int8_t和u_int32_t替换为标准的uint8_t和uint32_t
 移除了hmap_new函数中的return语句（因为返回类型为 void）
 修复了函数声明和定义不一致的问题

 核心问题修复：
 在 hmap_node_t 中增加了 key_copied 标志位，用于记录键是否通过 strdup 复制
 在 hmap_remove 中，仅当 key_copied 为 true 时才释放键（避免释放外部传入的栈内存键）
 完善了空指针检查，防止对 NULL 指针进行操作
 其他优化：
 增强了边界条件处理（如空哈希表、空键、无效容量等）
 优化了迭代器逻辑，避免越界访问
 完善了 hmap_free 中的内存释放逻辑，确保所有复制的键都被正确释放
 */
